集合論（Set Theory）

集合（Set）

將數個物件依照某個特性集合成的群體，群體中的個體稱為「元素」（element），常以大寫字母 A、B、C、S 等表示，元素則多以小寫字母 a、b、c、s 表示。

「集合」與「元素」的關係

若一元素 a 屬於某集合 A，記為「a∈A」；若另一元素 b 不屬於集合 A，記為「b∉A」。例如「√3」屬於「實數」這個集合，可記為「√3∈R」；「√3」不屬於「整數」這個集合，可記為「√3∉Z」。

若用 a、b、c、s 這四個元素屬於「A」這個集合，記為「A={a,b,c,s}」，也可以用謂詞搭配量詞表示，例如「B={x|(∀x)[x>5，x∈Z]} 代表「對於所有大於 5 的整數 x」這個集合。

集合的「基數（cardinal number）」

代表集合中元素的數量，如果一集合的基數為零，稱為「空集（empty set）」，記為「∅」或「{}」。

表示一集合 A 的基數可用下列符號表示，本文將以第一種為主：

1. |A|
2. #A
3. A̅
4. A̿
5. Card(A)

集合間的關係

當有一個以上的集合時，可探討不同集合間的關係，一般常用「文氏圖（Venn diagram）」表示。

一、子集（subset）

若一集合 A 屬於另一集合 B，A 的每個元素都是 B 的元素，但 B 的元素不一定全部屬於 A，則 A 稱為 B 的「子集（subset）」，記為「A⊆B」，B 是 A 的「超集（superset）」，記為「B⊇A」。

在表示「子集」與「超集」的關係時，符號開口端固定朝向元素數量較多的「超集」。

A⊆B、B⊇A

「數」的集合關係

在數學中，有「N⊆Z⊆Q⊆R⊆C」這層關係，每個符號分別代表的意義如下：

• N：代表「自然數（natural number）」
• Z：代表「整數（integer）」
• Q：代表「有理數（rational number）」
• R：代表「實數（real number）」
• C：代表「複數（complex number）」

NZQRC關係圖

二、宇集／全集（universe） & 補集（complement）

「宇集」指一包含所有研究對象的集合，未包含在其特定子集者形成的集合稱為「補集／絕對差集（absolute complement）」。

宇集與補集的關係

給定一宇集 U，補集代表屬於 U、但不屬於 U 中另一集合 A 的元素所成的集合，記為「Aᶜ」。

例如若要研究複數時，以「C」這個集合為宇集，選擇當中的實數「R」為子集，「屬於複數，但不屬於實數」的集合「Rᶜ」即為「補集」。

複數（C）為宇集，Rᶜ 為實數（R）的補集

三、交集（intersection）& 聯集（union）

概念與「命題」類似，但符號較為圓滑，以「∩」表示「交集」、「∪」表示「聯集」。

左圖深藍處代表「A∩B」、右圖深藍處代表「A∪B」

有了「交集」與「聯集」表示兩集合間的關係，則可以整理出下列特性：

一集合 A 與空集 ∅ 及宇集 S 的關係：

1. (Aᶜ ∩ A) = ∅
2. (Aᶜ ∪ A) = S
3. (A ∩ S) = A
4. (A ∪ ∅) = S

兩集合 A、B 間的笛摩根定律：

1. (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
2. (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

四、差集／相對差集（relative complement）

指數個集合中，屬於某集合但不屬於其他集合的元素所成的集合，記為「\」或「–」。

例如有兩個集合 A、B，若集合 A 代表 30 的因數、集合 B 代表 20 的因數，則 B 在 A 的差集代表「是 30 的因數、但不是 20 的因數」這個集合，記為「A\B」或「A–B」，又可以記為「A∩Bᶜ」，該差集為 {3,6,15,30}。

相對的，A 在 B 的差集代表「是 20 的因數、但不是 30 的因數」這個集合，記為「B\A」或「B–A」，又可以記為「B∩Aᶜ」，該差集為 {4,20}。

左圖深藍處為「A\B」、右圖深藍處為「B\A」

五、對稱差集（symmetric difference）

指僅屬於單一集合、不屬於其他集合的集合，也就是聯集扣除交集形成的集合，計為「Δ」。

以上述「30 的因數為 A 集合、20 的因數為 B 集合」來說，兩者的對稱差集「AΔB」即為「(A∪B)–(A∩B)」，代表「僅為 30 的因數」與「僅為 20 的因數」形成的集合，包含 {3,4,6,15,20,30}。

深藍處代表「AΔB」

排容原理（inclusion–exclusion principle）

數個集合中，若要找到其聯集基數，可用反覆扣除交集、再加回反覆扣除的交集求得。

一、兩個集合的排容

將兩集合 A、B 相加後，扣除重複計算的交集部分，可得聯集「A∪B」，即「(|A∪B|)=(|A|+|B|)–(|A∩B|)」。

二、三個集合的排容

將兩集合 A、B 相加後，扣除兩集合間的交集，再加回重複扣除的三集合交集可得聯集「A∪B∪C」，即「(|A∪B∪C|)=(|A|+|B|+|C|)–(|A∩B|+|B∩C|+|A∩C|)+(|A∩B∩C|)」。

三、n 個集合的排容

將所有集合相加後，扣除重複計算的交集、再加回反覆扣除的交集，重複操作到每個交集都剛好計算到一次為止。

對於集合 A₁、A₂、...、Aₙ 而言，其排容過程可用下列公式表示：

四、排容原理應用－歐拉函數（Euler’s totient function）

「歐拉函數」代表對於一個正整數 n，所有小於等於 n 的正整數中，與 n 互質的數的數量，記為「φ」，例如 10 有 1、3、7、9 四個正整數與其互質，因此 φ(10)=4。

當一個正整數變得很大時，若要一一透過找出與其互質的數來求得其 φ 值，將會顯得不切實際，此時便可用「排容原理」與「補集」的觀念求解。

用「排容原理」求歐拉函數

舉例來說，如果要求 φ(120)，可以先將 120 做質因數分解，求得 120=2³·3¹·5¹，根據算術基本定理，這樣的分解方式是唯一的。

所有與 120 互質的數必不是 2 的倍數、不是 3 的倍數、也不是 5 的倍數，即下圖淺色底的外圍區域。

根據上圖，與 120 互質的數即在宇集為 1~120 的集合中，「A∪B∪C」的補集，即 φ(120)=120–[(|A|+|B|+|C|)–(|A∩B|+|B∩C|+|A∩C|)+(|A∩B∩C|)]。

1. |A|=120/2=60、|B|=120/3=40、|C|=120/5=24
2. |A∩B|=120/6=20、|B∩C|=120/15=8、|A∩C|=120/10=12
3. |A∩B∩C|=120/30=4

φ(120)=120–[(60+40+24)–(20+8+12)+(4)]=120–88=32

用「排容原理」求歐拉函數的推廣

根據上述 φ(120) 的範例，可以假設若一數有三個質因數，則可以寫成下列關係式：

根據上述集合論關係圖，可得下列關係式：

將每一項通分，得：

將n提出來，得：

分子經整理，可得下列關係式：

這就是 n 有三個質因數時的歐拉函數公式！

類似的概念可推廣至一正整數 n 有 k 個質因數 P₁、P₂、…、Pₖ 時，該正整數 n=P₁ˣ¹ · P₂ˣ² ‧ … ‧ Pₖˣᵏ，則其歐拉函數公式如下：

上述公式的完整證明過程可參考維基百科。

笛卡爾積（Cartesian product）

代表全部有序對形成的集合，該有序對中的對象分別為不同集合的元素，以「×」表示，如「A 集合與 B 集合的笛卡爾積」記為「A × B」。

舉例來說，若 A 集合為 {1,2}、B 集合為 {a,b,c}，則 A × B = {{1,a},{1,b},{1,c},{2,a},{2,b},{2,c}}，「A 集合中的每個元素」各自與「B 集合中的每個元素」配對。

範例 A 集合與範例 B 集合的「笛卡爾積」

笛卡爾積的應用：SQL

在「結構化查詢語言（SQL）」中使用「交叉連接（cross join）」時，將回傳兩筆資料的笛卡爾積。

鴿巢原理（pigeonhole principle）

若 A 集合有 (n+1) 個元素、B 集合有 n 個元素，則不存在 A 到 B 的單射（injection）。

也就是說，B 集合中一定會有元素跟兩個以上 A 集合中的元素配對。

這樣講起來有點抽象，現在我們回歸原理名稱，換個生活化的情境理解：現假設 n=9，A 集合有 (9+1)=10 隻鴿子、B 集合有 9 個巢，那麼 B 集合中必定有一個巢會有兩隻鴿子。

「鴿巢原理」示意圖（取自維基百科）

鴿巢原理的應用：雜湊表／哈希表（hash table）

雜湊表可以依照鍵（key）值找到一資料的記憶體儲存位置，若記憶體共有 m 個儲存空間、資料共有 n 筆，則可定義「載荷因子（load factor）」如下：

如果 n 比 m 大，即載荷因子大於 1，要儲存的資料比可供儲存的空間還多，就會產生「雜湊衝突（collision）」，這就是「鴿巢原理」的應用情境。解決衝突的方式有封閉尋址（closed addressing / chaining）、開放定址（open addressing）等，詳細資訊可參考奮 game 王紫楓教學影片。

小結

1. 集合：一具有特定相似特徵的母體，由元素組成其個體，若一元素屬於某集合，可用「∈」表示兩者間關係，反之用「∉」，符號開口端皆朝集合。
2. 基數：代表集合內元素的數量。
3. 空集（∅）：基數為零的集合。
4. 子集：一集合中的另一集合，寫在「⊆」或「⊇」符號閉口端。
5. 超集：包含另一集合的集合，寫在「⊆」或「⊇」符號開口端。
6. 「數」的集合關係：N⊆Z⊆Q⊆R⊆C。
7. 宇集／全集：所有探討對象皆為其元素的集合。
8. 補集／絕對差集：宇集中，不包含在宇集內特定集合的集合。
9. 交集（∩）：數個集合間重疊處。
10. 聯集（∪）：包含數個集合間的重疊處與非重疊處。
11. 差集／相對差集（\ 或 –）：數個集合中，僅屬於特定集合、不屬於其他集合處。
12. 對稱差集（Δ）：數個集合間，所有僅屬於一個集合處加總。
13. 排容原理：計算數個集合聯集時，反覆扣除重複計算的交集、再加回重複扣除的交集，直到每個交集都只被計算一次。
14. 歐拉函數（φ）：表示與某一正整數互質的正整數數量，可用排容原理搭配補集觀念求解。
15. 笛卡爾積（×）：不同集合間的有序對形成的集合，可應用於 SQL。
16. 鴿巢原理：若一集合 A 的基數多於另一集合 B，則不存在 A 到 B 的單射，可應用於雜湊表。